昨天講完了遞迴的基本定義以及遞迴和非遞迴的差異
今天要來說說遞迴的經典題型：費式數列及河內塔
還不熟遞迴的記得回去複習！

費式數列（Fibonacci Series）

這個數列是由義大利數學家費波那契在他的《算盤書》中提出，定義為：

• F(0) = 0
• F(1) = 1
• F(N) = F(N - 2) + F(N - 1), 此處 N >= 2

簡單來說，這個數列的首項為 0，次項為 1，從第二項以後 = 前兩項相加。
列出幾個給大家看：
{Fibonacci}: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 ......

我們可以發現他的成長速率是非常快的

費式數列的程式碼

從數學定義可以看出，費式數列天生就長的一副欠遞迴的樣子：
費式數列 F(N) 的 Recursive Function:

int fib(int N){
    if(N == 0) return 0;
    if(N == 1) return 1;
    return fib(N - 1) + fib(N - 2);
}

如果是 Iterative Function的話：

int fib(int N){
    if(N == 0) return 0;
    if(N == 1) return 1;
    
    int a = 0, b = 1, c = 0;
    
    for(int i = 2; i <= N){
        c = a + b;
        a = b;
        b = c;
    }
    
    return c;
}

上面兩個程式碼完全驗證了 Recursive 就是比 Non-Recursive 容易解釋！

遞迴的問題

昨天說過，雖然遞迴的程式碼好看很多，但其實它的效率很差
而費式數列採用遞迴的最大問題是：重複執行了一堆一樣的遞迴項！
甚麼意思呢？我們拿第 5 項來舉例好了

Fib(5) 會等於 Fib(3) + Fib(4)
接著，Fib(4) 等於 Fib(2) + Fib(3)
Fib(3) 又會等於 Fib(2) + Fib(1)
Fib(2) 等於 Fib(0) + Fib(1)

我們現在可以來看看展開後會變成甚麼：
Fib(5) = Fib(3) + Fib(4) = Fib(3) + (Fib(2) + Fib(3))
= (Fib(1) + Fib(2)) + Fib(2) + (Fib(1) + Fib(2))

而這每一項都是一堆的遞迴 Function call！
根本都在重複做一樣的事情，導致效率超級差。
先偷跑一下明天會講的時間複雜度，這個程式碼會接近 O(2^n)指數型（執行次數隨著N的增加指數成長）
總之，效率非常差

而要解決這個狀況，就只能乖乖用 Iteration 了
可以透過 dynamic programming 的思維來解決
這是一種使用額外記憶體來避免重複計算的技術
簡單的說就是透過一個 Array 把已經算過的值存起來，重複使用

int fib(int N){
    int array[N + 1];
    array[0] = 0;
    array[1] = 1;
    for(int i = 2; i <= N; i++){
        array[i] = array[i - 1] + array[i - 2];
    }
    return array[i];
}

這樣比前一個的 Iteration 好解釋，而且時間複雜度也能達到 O(n)線性（執行次數隨著N的增加線性成長）

河內塔（Tower of Hanoi）

這其實是一個很好玩的遊戲，規則是這樣：
現在有三個底座，分別為 A 底座、B 底座及 C 底座。
今天 A 底座上有 N 個盤子，大小不一，且大盤子必須置於小盤子之下。
在一次只能搬動一個盤子的情況下，如何用最少次數將 A 底座的盤子，搬移至 C 底座
附上連結，大家能夠去玩玩看：傳送門

而為甚麼這個遊戲會跟遞迴有關係呢？
因為這個例子正好說明了演算法中 Divided and Conquer 的特性
也就是在設計演算法時，將本來的問題切割成數個子問題來一一解決。

在河內塔中，我們不需要去一一探討哪個盤子下一部應該要怎麼移。
我們只需要做：

1. 把上面的 N - 1 個盤子從起始底座搬到輔助底座
2. 把最下面，也就是最大的盤子移動到目標底座
3. 最後再將 N - 1 個盤子從輔助底座移到目標底座

而這個搬，是用「搬河內塔的方式搬」，也就是 Call 個遞迴就好。

結束了？！
對就這樣而已。
來看看程式吧：

void Hanoi(int n, char start, char aux, char end){
    if(n == 1){
        printf("move disk 1 from %c to %c\n", start, end);
        return;
    }else{
        Hanoi(n - 1, start, end, aux);
        printf("move disk %d from %c to %c\n", n, start, end);
        Hanoi(n - 1, aux, start, end);
    }
}

我們不要被參數的名字搞混了，解釋一下：
第一個參數填：要移動幾個盤子
第二個參數填：要從哪個底座移動
第三個參數填：要移動到哪個底座
第四個參數填：剩下的那個底座當作輔助

遞迴的終止條件為：如果 n = 1，代表不用在乎甚麼規則了，直接從起點搬到到目的地
那如果 n >= 2 呢，那麼就代表要遵守河內塔的規則了
也就像我們剛剛說的，先將 n - 1 個盤子搬到輔助底座，再搬最大的盤子，最後再把 n - 1 個盤子搬到目的地

大家能跑跑看這個程式，程式會自動把步驟列出來，告訴你應該怎麼搬喔。

這個遞迴程式一樣超級沒效率（時間複雜度：O(2^n)）

其實遞迴還有很多有趣的程式，但我覺得太多了，還有太多東西要講，遞迴就在這裡打住吧。
明天要來講時間複雜度分析，以及漸進式符號。